DROPS

Document

DOI: 10.4230/LIPIcs.CP.2023.34

Constraint Programming with External Worst-Case Traversal Time Analysis

Authors: Pierre Talbot, Tingting Hu, and Nicolas Navet

Published in: LIPIcs, Volume 280, 29th International Conference on Principles and Practice of Constraint Programming (CP 2023)

Abstract

The allocation of software functions to processors under compute capacity and network links constraints is an important optimization problem in the field of embedded distributed systems. We present a hybrid approach to solve the allocation problem combining a constraint solver and a worst-case traversal time (WCTT) analysis that verifies the network timing constraints. The WCTT analysis is implemented as an industrial black-box program, which makes a tight integration with constraint solving challenging. We contribute to a new multi-objective constraint solving algorithm for integrating external under-approximating functions, such as the WCTT analysis, with constraint solving, and prove its correctness. We apply this new algorithm to the allocation problem in the context of automotive service-oriented architectures based on Ethernet networks, and provide a new dataset of realistic instances to evaluate our approach.

Cite as

Pierre Talbot, Tingting Hu, and Nicolas Navet. Constraint Programming with External Worst-Case Traversal Time Analysis. In 29th International Conference on Principles and Practice of Constraint Programming (CP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 280, pp. 34:1-34:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{talbot_et_al:LIPIcs.CP.2023.34,
  author =	{Talbot, Pierre and Hu, Tingting and Navet, Nicolas},
  title =	{{Constraint Programming with External Worst-Case Traversal Time Analysis}},
  booktitle =	{29th International Conference on Principles and Practice of Constraint Programming (CP 2023)},
  pages =	{34:1--34:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-300-3},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{280},
  editor =	{Yap, Roland H. C.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2023.34},
  URN =		{urn:nbn:de:0030-drops-190713},
  doi =		{10.4230/LIPIcs.CP.2023.34},
  annote =	{Keywords: Constraint programming, external function, multi-objective optimization, network analysis, worst-case traversal time analysis, abstract interpretation}
}

Search Results

Documents authored by Hu, Tingting

Constraint Programming with External Worst-Case Traversal Time Analysis

Abstract

Cite as

Thanks for your feedback!

Could not send message